package algorithm.sort.review;

import java.util.Arrays;

public class Merge {

    public static void main(String[] args) {
        int[] arr = {19, 97, 9, 17, 1, 8, 27};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int[] arr){
        int[] temp = new int[arr.length];
        sort(arr,0,arr.length-1,temp);
    }
    public static void sort(int[] arr, int l,int r,int[] temp){
        if (l<r){
            int mid = (l+r)/2;
            sort(arr,l,mid,temp);
            sort(arr,mid+1,r,temp);
            merge(arr,l,mid,r,temp);
        }
    }
    public static void merge(int[] arr,int l,int mid, int r,int[] temp){
        int i = l;
        int j = mid+1;
        int k = 0;
        while (i <= mid && j <= r){
            if (arr[i] < arr[j]){
                temp[k++] = arr[i++];
            }else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid){
            temp[k++] = arr[i++];
        }
        while (j <= r){
            temp[k++] = arr[j++];
        }
        k = 0;
        while (l<=r){
            arr[l++] = temp[k++];
        }
    }
}
